The coverability and boundedness problems for Petri nets are known to beExpspace-complete. Given a Petri net, we associate a graph with it. With thevertex cover number k of this graph and the maximum arc weight W as parameters,we show that coverability and boundedness are in ParaPspace. This means thatthese problems can be solved in space O(ef(k,W)poly(n)), where ef(k,W) is someexponential function and poly(n) is some polynomial in the size of the input.We then extend the ParaPspace result to model checking a logic that can expresssome generalizations of coverability and boundedness.
展开▼
